| Does every bridgeless graph have a multiset of cycles covering every edge exactly twice? |
In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.
It is an unsolved problem, posed by George Szekeres[1] and Paul Seymour[2] and known as the cycle double cover conjecture, whether every bridgeless graph has a cycle double cover. The conjecture can equivalently be formulated in terms of graph embeddings, and in that context is also known as the circular embedding conjecture.
Contents |
The usual formulation of the cycle double cover conjecture asks whether every bridgeless undirected graph has a collection of cycles such that each edge of the graph is contained in exactly two of the cycles. The requirement that the graph be bridgeless is an obvious necessary condition for such a set of cycles to exist, because a bridge cannot belong to any cycle. A collection of cycles satisfying the condition of the cycle double cover conjecture is called a cycle double cover. Some graphs such as cycle graphs and bridgeless cactus graphs can only be covered by using the same cycle more than once, so this sort of duplication is allowed in a cycle double cover.
A snark is a special case of a bridgeless graph, having the additional properties that every vertex has exactly three incident edges (that is, the graph is cubic) and that it is not possible to partition the edges of the graph into three perfect matchings (that is, the graph has no 3-edge coloring, and by Vizing's theorem has chromatic index 4). It turns out that snarks form the only difficult case of the cycle double cover conjecture: if the conjecture is true for snarks, it is true for any graph.[3]
Jaeger (1985) observes that, in any potential minimal counterexample to the cycle double cover conjecture, all vertices must have three or more incident edges. For, a vertex with only one edge incident forms a bridge, while if two edges are incident on a vertex, one can contract them to form a smaller graph such that any double cover of the smaller graph extends to one of the original graph. On the other hand, if a vertex v has four or more incident edges, one may “split off” two of those edges by removing them from the graph and replacing them by a single edge connecting their two other endpoints, while preserving the bridgelessness of the resulting graph. Again, a double cover of the resulting graph may be extended in a straightforward way to a double cover of the original graph: every cycle of the split off graph corresponds either to a cycle of the original graph, or to a pair of cycles meeting at v. Thus, every minimal counterexample must be cubic. But if a cubic graph can have its edges 3-colored (say with the colors red, blue, and green), then the subgraph of red and blue edges, the subgraph of blue and green edges, and the subgraph of red and green edges each form a collection of disjoint cycles that together cover all edges of the graph twice. Therefore, every minimal counterexample must be a non-3-edge-colorable bridgeless cubic graph, that is, a snark.[3]
One possible attack on the cycle double cover problem would be to show that there cannot exist a minimum counterexample, by proving that any graph contains a reducible configuration, a subgraph that can be replaced by a smaller subgraph in a way that would preserve the existence or nonexistence of a cycle double cover. For instance, if a cubic graph contains a triangle, a Δ-Y transform will replace the triangle by a single vertex; any cycle double cover of the smaller graph can be extended back to a cycle double cover of the original cubic graph. Therefore, a minimal counterexample to the cycle double cover conjecture must be a triangle-free graph, ruling out some snarks such as Tietze's graph which contain triangles. Through computer searches, it is known that every cycle of length 11 or less in a cubic graph forms a reducible configuration, and therefore that any minimal counterexample to the cycle double cover conjecture must have girth at least 12.[4]
Unfortunately, it is not possible to prove the cycle double cover conjecture using a finite set of reducible configurations. Every reducible configuration contains a cycle, so for every finite set S of reducible configurations there is a number γ such that all configurations in the set contain a cycle of length at most γ. However, there exist snarks with arbitrarily high girth, that is, with arbitrarily high bounds on the length of their shortest cycle.[5] A snark G with girth greater than γ cannot contain any of the configurations in the set S, so the reductions in S are not strong enough to rule out the possibility that G might be a minimal counterexample.
If a graph has a cycle double cover, the cycles of the cover can be used to form the 2-cells of a graph embedding onto a two-dimensional cell complex. In the case of a cubic graph, this complex always forms a manifold. The graph is said to be circularly embedded onto the manifold, in that every face of the embedding is a simple cycle in the graph. However, a cycle double cover of a graph with degree greater than three may not correspond to an embedding on a manifold: the cell complex formed by the cycles of the cover may have non-manifold topology at its vertices. The circular embedding conjecture or strong embedding conjecture[3] states that every biconnected graph has a circular embedding onto a manifold. If so, the graph also has a cycle double cover, formed by the faces of the embedding.
For cubic graphs, biconnectivity and bridgelessness are equivalent. Therefore, the circular embedding conjecture is clearly at least as strong as the cycle double cover conjecture. However, it turns out to be no stronger. If the vertices of a graph G are expanded to form a cubic graph, which is then circularly embedded, and the expansions are undone by contracting the added edges, the result will be a circular embedding of G itself. Therefore, if the cycle double cover conjecture is true, every biconnected graph has a circular embedding. That is, the cycle double cover conjecture is equivalent to the circular embedding conjecture, even though a cycle double cover and a circular embedding are not always the same thing.[3]
If a circular embedding exists, it might not be on a surface of minimal genus: Nguyen Huy Xuong described a biconnected toroidal graph none of whose circular embeddings lie on a torus.[3]
A stronger version of the circular embedding conjecture that has also been considered is the conjecture that every biconnected graph has a circular embedding on an orientable manifold. In terms of the cycle double cover conjecture, this is equivalent to the conjecture that there exists a cycle double cover, and an orientation for each of the cycles in the cover, such that for every edge e the two cycles that cover e are oriented in opposite directions through e.[3]
Alternatively, strengthenings of the conjecture that involve colorings of the cycles in the cover have also been considered. The strongest of these is a conjecture that every bridgeless graph has a circular embedding on an orientable manifold in which the faces can be 5-colored. If true, this would imply a conjecture of W. T. Tutte that every bridgeless graph has a nowhere-zero 5-flow.[3]
A stronger type of embedding than a circular embedding is a polyhedral embedding, an embedding of a graph on a surface in such a way that every face is a simple cycle and every two faces that intersect do so in either a single vertex or a single edge. (In the case of a cubic graph, this can be simplified to a requirement that every two faces that intersect do so in a single edge.) Thus, in view of the reduction of the cycle double cover conjecture to snarks, it is of interest to investigate polyhedral embeddings of snarks. Unable to find such embeddings, Branko Grünbaum conjectured that they do not exist, but Kochol (2009a, 2009b) disproved Grünbaum's conjecture by finding a snark with a polyhedral embedding.